import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

/**
 * solve the percolation problem
 * @author lichao
 * @date 2017-03-26
 */
public class Percolation {
	private int sideLength; // the grid side length
	private int[] open; // array mark site if open,1 means open,0 means blocked 
	private WeightedQuickUnionUF quickUnionUF; // process the union and connected operations
	private int openNum; // count open sites 
	private int virtualTop,virtualBottom; // virtual top/bottom site
	

	// create n-by-n grid, with all sites blocked
	public Percolation(int n) {
		if(n<=0) throw new IllegalArgumentException("argument " + n + "is not greater than 0");
		sideLength = n;
		// the sites number (contains virtualTop/virtualBottom sites)
		int size = n * n + 2;
		virtualTop = 0;virtualBottom = n * n + 1;// set the virtual top/bottom site
		// initialize open array with default 0
		open = new int[size];
		quickUnionUF = new WeightedQuickUnionUF(size);
		for(int i=1;i<=n;i++){
			quickUnionUF.union(virtualTop, xyTo1D(1, i));// union virtual top site of first row
			quickUnionUF.union(virtualBottom, xyTo1D(n, i));// union virtual bottom site of last row 
		}
	}
	
	// open site (row, col) if it is not open already
	public void open(int row, int col) {
		validate(row, col);
		if(isOpen(row, col)) return;
		int i = xyTo1D(row, col);
		open[i] = 1; // mark open
		if(row >= 2 && isOpen(row-1,col)) quickUnionUF.union(i, xyTo1D(row-1, col)); // union top
		if(col >= 2 && isOpen(row, col-1)) quickUnionUF.union(i, xyTo1D(row, col-1)); // union left
		if(row <= (sideLength-1) && isOpen(row+1, col)) quickUnionUF.union(i, xyTo1D(row+1, col)); // union bottom
		if(col <= (sideLength-1) && isOpen(row, col+1)) quickUnionUF.union(i, xyTo1D(row, col+1)); // union right
		openNum++;
	}
	
	// is site (row, col) open?
	public boolean isOpen(int row, int col) {
		validate(row, col);
		return open[xyTo1D(row, col)] == 1;
	}
	
	// is site (row, col) full?
	public boolean isFull(int row, int col){
		return isOpen(row, col) && quickUnionUF.connected(virtualTop, xyTo1D(row, col));
	}
	
	// number of open sites
	public int numberOfOpenSites(){
		return openNum;
	}
	
	// does the system percolate?
	public boolean percolates(){
		return quickUnionUF.connected(virtualTop, virtualBottom);
	}
	
	// map the 2D coordinates to 1D coordinates
	private int xyTo1D(int x, int y){
		return (x - 1) * sideLength + y; 
	}
	
	// validate the row and col is a valid index
	private void validate(int row, int col){
		if (row < 1 ||  row > sideLength) 
            throw new IndexOutOfBoundsException("row " + row + " is not between 1 and " + sideLength);  
		if (col < 1 ||  col > sideLength)
            throw new IndexOutOfBoundsException("col " + col + " is not between 1 and " + sideLength);  
	}

	// test client (optional)
	public static void main(String[] args){
		Percolation p = new Percolation(10);
		p.open(1, 1);
		p.open(2, 2);
		StdOut.println(p.quickUnionUF.connected(1, 1));
	}
}
